package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.Arrays;

public class e4字符串匹配SuffixArrayNotStaticPlus倍增法改进Plus高度数组 {
	public static void main(String[] args) {
		String mother = "ABABABABB";
		String mother2 = "ABCABC";
        String child = "BABB";
        e4字符串匹配SuffixArrayNotStaticPlus倍增法改进Plus高度数组 test = new e4字符串匹配SuffixArrayNotStaticPlus倍增法改进Plus高度数组();
        int[] array = test.makeHeightArray(mother2, test.makeSuffixArrayUpdate(mother2));
        for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
	
	/**
	高度数组height[]
	height[i]的数值是已排序的suffArray中，suffArray[i]对于suffArray[i - 1]，在两字符片段的前缀中的最大重合元素数；真他妈了个比的绕
	
	如果已经知道已排序的suffArray中的索引i与i+1的lcp为h,那么i代表的字符串与i+1代表的字符串去掉首字母后的lcp为h-1.
	根据上述，我们可以发现：
		如果知道未排序的suffArray中索引i的suff的lcp为k, 那么“suff去掉首字母后的新字符片段(newsuff)与newsuff” 对于 “已排序的suffArray中相对于newsuff前一个索引的元素prenewsuff”的lcp >= k-1.
		例如对于字符串abcabc:
			我们知道abcabc(未排序的suffArray中索引0) 对于 abc(未排序的suffArray中索引3)的lcp为3.
			那么bcabc(未排序的suffArray中索引1) 对于 bc(未排序的suffArray中索引4)的lcp >= 3-1.
		利用这一点就可以O(N)求出高度数组
	O(N)
	将来的我要是看不懂就去死记硬背吧
	 * @param string
	 * @param suffArray
	 * @return
	 */
	public int[] makeHeightArray(String string, Suff[] suffArray) {
		int length = string.length();
		int[] rk = new int[length];
		int[] height = new int[length];
		int k = 0;
		for (int i = 0; i < length; i++) {//根据已排序的suffArray[]重新生成rk[]
			rk[suffArray[i].getIndex()] = i;
		}
		for (int memberVariable_Index = 0; memberVariable_Index < length; memberVariable_Index++) {//开始填充height[]；memberVariable_Index代表index成员变量,也代表最初原始的后缀数组的索引
			int locationOfRankAlsoIndexOfSuffArray = rk[memberVariable_Index];//当前索引memberVariable_Index的rk[]值；同时也是已排序的suffArray[]的索引
			if (locationOfRankAlsoIndexOfSuffArray == 0) {//若rk[]值 = 0；代表此suff是suffArray[]的首元素，
				height[0] = 0;//那么此suff的height[]值 = 0；
				continue;
			}
			int locationPreAlsoIndexPre = locationOfRankAlsoIndexOfSuffArray - 1;//suffArray[]中locationOfRankAlsoIndexOfSuffArray索引的上一个索引；同时也是rk[]中locationOfRankAlsoIndexOfSuffArray位置的上一个位置；能走到这里locationOfRankAlsoIndexOfSuffArray一定 > 0了
			int memberVariable_PreIndex = suffArray[locationPreAlsoIndexPre].getIndex();//根据suffArray[]的索引locationPreAlsoIndexPre，找到目标suff并获取目标suff的index变量(同时也是目标suff在最初原始的后缀数组的索引)
			if (k > 0) {//因为公式height[rk[i + 1]] >= height[rk[i]] - 1；k就代表height[rk[i]]
				k--;//所以如果k > 0就让 k - 1
			}
			while (memberVariable_PreIndex + k < length && memberVariable_Index + k < length) {//跳出条件是：某字符片段索引越界
				if (string.charAt(memberVariable_PreIndex + k) != string.charAt(memberVariable_Index + k)) {//跳过k个元素，换言之从第k索引开始逐个比较两“字符片段”
					break;
				}
				k++;//k的数值就是相等字符的数量
			}
			height[locationOfRankAlsoIndexOfSuffArray] = k;//当前suffArrray[]的索引locationOfRankAlsoIndexOfSuffArray的height[]值 = k
		}
		return height;
	}
	
	/**
	 * O(N*logN*logN + N*logM)
	 * @param mother
	 * @param child
	 */
	public void suffixArrayMatchUpdate(String mother, String child) {
		Suff[] suffixArray = makeSuffixArrayUpdate(mother);
		int l = 0;
		int r = mother.length() - 1;
		while (r >= l) {
			int mid = l + ((r - l) >>> 1);
			int compareResult = 0;
			String suffMid = mother.substring(suffixArray[mid].getIndex(), r + 1); 
			if (suffMid.length() >= child.length()) {
				compareResult = suffMid.substring(0, child.length()).compareTo(child);
			} else {
				compareResult = suffMid.compareTo(child);
			}
			if (compareResult == 0) {
				System.out.println("index:" + suffixArray[mid].getIndex());
				return;
			} else if (compareResult < 0) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		System.out.println("没找到,输出所有的后缀数组：");
		printSuffixArray(suffixArray);
	}
	
	/**
	 * O(N*logN*logN)
	 * @param string
	 * @return
	 */
	public Suff[] makeSuffixArrayUpdate(String string) {
		int length = string.length();
		int[] rk = new int[length];
		Suff[] suffixArray = new Suff[length];
		for (int i = 0; i < length; i++) { 
			suffixArray[i] = new Suff(string.charAt(i) + "", i);
		}
		Arrays.sort(suffixArray); 
		rk[suffixArray[0].getIndex()] = 1; 
		for (int i = 1; i < length; i++) { 
			rk[suffixArray[i].getIndex()] = rk[suffixArray[i - 1].getIndex()];
			if (!suffixArray[i].getString().equals(suffixArray[i - 1].getString())) { 
				rk[suffixArray[i].getIndex()]++;
			}
		}
		for (int k = 2; rk[suffixArray[length - 1].getIndex()] < length; k *= 2) {
			final int kk = k;
			Arrays.sort(suffixArray, (o1, o2) -> { 
				int x = ((Suff) o1).getIndex();
				int y = ((Suff) o2).getIndex();
				if (rk[x] == rk[y]) {
					if (x + kk / 2 >= length || y + kk / 2 >= length) { 
						return -(x - y);
					}
					return rk[x + kk / 2] - rk[y + kk / 2];
				} else {
					return rk[x] - rk[y];
				}
			});
			rk[suffixArray[0].getIndex()] = 1; 
			for (int i = 1; i < length; i++) {
				int i1 = suffixArray[i].getIndex(); 
				int i2 = suffixArray[i - 1].getIndex(); 
				rk[i1] = rk[i2]; 
				try {
					if (!string.substring(i1, i1 + kk).equals(string.substring(i2, i2 + kk))) { 
						rk[i1]++;
					}
				} catch (Exception e) {
					rk[i1]++; 
				}
			}
		}
		return suffixArray; 
	}
	
	public void printSuffixArray(Suff[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
	
	public class Suff implements Comparable<Suff> {
		private String string = null;
		private int index = 0;
		public Suff() {};
		public Suff(String string, int index) {
			this.string = string;
			this.index = index;
		}
		public void setString(String string) {
			this.string = string;
		}
		public String getString() {
			return this.string;
		}
		public void setIndex(int index) {
			this.index = index;
		}
		public int getIndex() {
			return this.index;
		}
		@Override
		public int compareTo(Suff other) {
			return this.string.compareTo(other.string);
		}	
		@Override
        public String toString() {
            return "Suff {" +
                    "string='" + string + '\'' +
                    ", index=" + index +
                    '}';
        }
	}
}
